package com.kobeliu.entity;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * leetcode 15
 *
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 */
public class Demo_16_No15 {

    public static void main(String[] args) {

        int[] nums = {1,2,-2,-1};

        List<List<Integer>> lists = threeSum(nums);
        for (int i = 0; i < lists.size(); i++) {
            System.out.println(lists.get(i));
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        //做一个归并排序
        int left = 0;
        int right = 0;

        //排序的意义 是为了后面的去重
        Mergesort(nums,0,nums.length-1);
        for (int i = 0; i < nums.length-2; i++) {
            int j = i+1; //左边的指针
            int k = nums.length-1; //右边的指针

            while(j<k && k>i){
                if(i>0 && nums[i]==nums[i-1]) continue; //去重
                if(nums[i]>0) break; //因为是排过序的，所以i位置大于零，后面的位置也都大于0
                int sum = nums[i]+nums[j]+nums[k];
                if(sum==0){
                    lists.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    //这两句需要理解,去重
                    while(j<k && nums[j]== nums[j+1]) j++;
                    while(j<k && nums[k]== nums[k-1]) k--;
                    j++;
                    k--;
                }else if(sum<0){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return lists;
    }
    private static void Mergesort(int[] nums, int low, int high) {
        if(low < high){
//            int mid = (high + low)/2;
            int mid = low + ((high - low)>>1); //>>的优先即
            Mergesort(nums,low,mid);
            Mergesort(nums,mid+1,high);
            merge(nums,low,mid,high);
        }
    }
    private static void merge(int[] nums, int low, int mid, int high) {
        int[] help = new int[high-low+1];
        int p = low; //左数组指针
        int q = mid+1; //右数组指针
        int i = 0; //help数组指针
        while(p<=mid && q<=high){
            help[i++] = nums[p] < nums[q] ? nums[p++]:nums[q++];
        }
        while(p<=mid){
            help[i++] = nums[p++];
        }
        while(q<=high){
            help[i++] = nums[q++];
        }
        for (int j = 0; j < i; j++) {
            nums[low+j] = help[j];
        }
    }
}
